![]() |
The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson Wiley Computer Publishing, John Wiley & Sons, Inc. ISBN: 0471353817 Pub Date: 03/01/99 |
Previous | Table of Contents | Next |
Extracting g Values. Once we have this triple (L0, R0, L1), we also have two relations on F: F(L0) = R0 ⊕ L1 and F(LN) = RN ⊕ LN+1. Note, however, that we do not yet have direct g values. Instead, we have two instances of the results of combining two g outputs with a PHT. Since we have the actual PHT output values, we can simply undo the PHT, yielding relations on g. Our pair has given us two relations on F, and thus four relations on g.
Extracting the S-boxes. The g outputs are the result of applying four key-dependent S-boxes to the input bytes, and then combining those bytes with an MDS matrix multiply. Since the MDS multiply is invertible, we invert it to get back the actual S-box outputs for all four different values. If those values are all different, then we have four bytes of output from each S-box. We can try all 232 possible key input values for each S-box, and see which ones are consistent with the results; for most sets byte values, only one or two S-boxes will match them. We thus learn each key-dependent S-box in g, perhaps with a couple of alternative values. We try all possible alternatives against any plaintext/ciphertext values we have available, and very quickly recover the correct S-boxes. Since this is the only key material in this Twofish variant, the attack is done.
We decided early in the design process to use purely bijective S-boxes. One rationale was to ensure that the 64-bit round function is bijective. That way, iterative 2-round differential characteristics cannot exist; when they do exist, they often result in the highest-probability multi-round characteristic, so avoiding them should help to reduce the risk of a successful differential attack. Also, attacks based on non-surjective round functions [BB95, RP95b, RPD97, CWSK98] are sure to fail when the 64-bit Feistel round function is bijective.6
6Vaudenays attack on Blowfish took advantage of non-bijectivity in the Blowfish round function [Vau96a].
We argue here that this was a good design decision, by showing that a Twofish variant that uses non-bijective S-boxes is likely to be much easier to break.
Observe that when q0 and q1 are non-bijective, their 3-way composition into si is likely to be even more non-surjective than either q0 or q1 on its own. It is easily seen that the expected size of the range of a random function on eight bits (such as q0 or q1) is r1 = 1 - (1 - (1 - 1/256)256 ≈ 1 - e-1 ≈ 0.632. When we compose such a function twice, its expected range becomes r2 = 1 - (1 - 1/256)256r1, ≈ 1-e-r1 ≈ 0.469; and the expected size of the range of a 3-way composition will be rs ≈ 1 - e-r2 ≈ 0.374. In other words, we expect that only about 96 ≈ 0.374 × 256 of all possible 8-bit values can appear as the output of the S-box. Therefore, the output of the h function can attain only about 226.3 ≈ 964 possible values, and the 64-bit Feistel function can attain only about 252.6 of all 264 possible outputs. This is certainly a rather large certificational weakness. (This gets worse when the key size grows, since the number of compositions of the q functions gets larger.)
We point out a serious differential attack when using non-bijective random S-boxes. Consider the probability pΔx that a given input difference Δx yields a collision in the S-box output; i.e., Δx → 0. Let p = ςΔx≠0 pΔx/255 be the average probability over all non-zero input differences, and let m = maxΔx≠0 pΔx be the maximum probability over all non-zero input differences. We have Ep = 3/256; also, Pr(p ≥ 2/256) ≈ 0.78, Pr(p ≥ 10/256) ≈ 0.02, and Pr(p ≥ 16/256) ≈ 0.0002. As for the distribution of m, empirically Em ≈ 11.7/256; experiments suggest Pr(m ≥ 10/256) ≈ 0.975, Pr(m ≥ 16/256) ≈ .04, and Pr(m ≥ 22/256) ≈ 0.0002.
Consider a Twofish variant with random non-bijective S-boxes and no rotations. We obtain a 2-round iterative differential characteristic with probability m, and thus a 13-round differential characteristic with probability m6.
We find that, for 97.5 percent of the keys, one can break the variant with about 228 chosen plaintexts; for 4 percent of the keys, it can be broken with 224 chosen plaintexts; and for a class of weak keys consisting of 0.02 percent of the keys, the variant cipher can be broken with roughly 221 chosen plain-texts. (Of course, one can trade off the number of texts needed against the size of the weak key class; the figures given are just examples of points on a smooth curve.)
Next we consider a Twofish variant with random non-bijective S-boxes, but with all rotations left intact. If we look at any 2-round differential characteristic whose first round is the trivial characteristic and whose second round involves just one active S-box, we expect its probability to be about p. One difficulty is that the rotations prevent us from finding an iterative 2-round characteristic. However, we can certainly piece together 6.5 different 2-round differential characteristics (each of the right form so it will have probability about p) to find a 13-round characteristic with expected probability p6. (The latter probability can probably be improved to about 3p6, due to the extra degrees of freedom, but as we are only doing a back-of-the-envelope estimate anyway, we will omit these considerations.) Thus, we can find a differential attack that succeeds with about 239 chosen plaintexts for the majority (about 78 percent) of the keys; also, for 2 percent of the keys, this variant can be broken with 228 chosen plaintexts; and for a class of weak keys consisting of 0.02 percent of the keys, the variant cipher can be broken with roughly 224 chosen plaintexts.
This analysis clearly shows the value of bijective S-boxes in stopping differential cryptanalysis. Also, it helps show the benefit of the rotations: they make short iterative characteristics much harder to find, thereby conferring (we hope) some additional resistance against differential attacks.
We assert that Twofish has no trap doors. As designers, we have made every effort to make Twofish secure against all known (and unknown) cryptanalysis, and we have made no effort to build in a secret way of breaking Twofish. However, there is no way to prove this, and not much reason for anyone to believe us. We can offer some assurances.
In this book, we have outlined all of the design elements of Twofish and our justifications for including them. We have explained, in great detail, how we chose Twofishs magic constants: the RS code, q0, q1 and the MDS matrix. There are no mysterious design elements; everything has an explicit purpose. Moreover, we feel that the use of key-dependent S-boxes makes it harder to install a trap door into the cipher. As difficult as it is to create a trap door for a particular set of carefully constructed S-boxes, it is much harder to create one that works with all possible S-boxes or even a reasonably useful subset of them (of relative size 2-20 or so).
Additionally, any trap door would have to survive 16 rounds of Twofish. It would have to work even though there is almost perfect diffusion in each round. It would have to survive the pre- and post-whitening. These design elements have long been known to make any patterns difficult to detect; trap doors would be no different.
None of this constitutes a proof. Any reasonable proof of general security for a block cipher would also prove P ≠ NP. Rather than outlining the proof here, we would likely skip the AES competition and go collect our Fields Medal.
However, we have made headway towards a philosophical proof. Assume for a moment that, despite the difficulties listed above, we did manage to put a trap door into Twofish. This would imply one of two things:
One, that we have invented a powerful new cryptanalytic attack and have carefully crafted Twofish to be resistant to all known attacks but vulnerable to this new one. We cannot prove that this is not true. However, we can point out that as cryptographers we would achieve much more fame and glory by publishing our powerful new cryptanalytic attack. In fact, we would probably publish it along with this paper, making sure Twofish is immune so that we can profitably attack the other AES submissions.
The other possibility is that we have embedded a trap door into the Twofish magic constants and then transformed them by some means so that finding them would be a statistical impossibility (see [Har96] for some discussion of this possibility). The resulting construction would seem immune to current cryptanalytic techniques, but we as designers would know a secret transformation rule that we could apply to facilitate cryptanalysis. Again, we cannot prove that this is not true. However, it has been shown that this type of cipher, called a master-key cryptosystem, is equivalent to a public-key cryptosystern [BFL96]. Again, as cryptographers we would achieve far greater recognition by publishing a public-key cryptosystem. that is not dependent on factoring [RSA78] or the discrete logarithm problem [DH76, E1G85, NIST94]. And the resulting algorithms dual capabilities as both a symmetric and public-key algorithm would make it far more flexible than the AES competition requires (and hence an excellent choice for the standard).
There is a large gap between a weakness that is exploitable in theory and one that is exploitable in practice. Even the best attack against DES (a linear-cryptanalysis-like attack combining quadratic approximations and a multiple-approximation method) requires just under 243 plaintext/ciphertext blocks [SK98], which is equivalent to about 64 terabytes of plaintext/ciphertext encrypted under a single key. A useful trap door would need to work with much less plaintexta few thousand blocksor it would have to reduce the effective keyspace to something on the order of 272. We believe that, given the quality of the public cryptanalytic research community, it would be impossible to put a weakness of this magnitude into a block cipher and have it remain undetected through the AES process. And we would be foolish to even try.
Previous | Table of Contents | Next |